Problem statement: zenit12ckj

Úloha s bludiskom bola jediná v krajskom kole, za ktorú nikto nezískal plný počet bodov. Čo bolo dobré, to stále dobré je, a preto dáme si repete!

Každý správny farmár musí vedieť hľadať cestu naprieč životnými prekážkami. A ak je život príliš ťažký alebo príliš ľahký, treba si prekážky prispôsobiť potrebám. V tejto úlohe budeme spomenuté životné princípy modelovať na probléme hľadania cesty v bludisku.

Bludiská budeme zapisovať v úplne rovnakom formáte ako na krajskom kole. Pre zopakovanie, korektné bludisko je dvojrozmerná mriežka znakov, ktorá spĺňa nasledovné požiadavky:

• Pozostáva len zo znakov '#' (stena), '.' (chodba), 'S' (štart) a 'C' (cieľ).
• Všetky znaky na obvode sú steny.
• Obsahuje práve jeden štart a práve jeden cieľ.

Pripomeňme si ešte, že krok medzi dvoma políčkami môžeme spraviť len vtedy, ak majú spoločnú stenu. Inými slovami, každé políčko má najviac štyroch susedov.

V tejto úlohe by sme chceli bludisko, v ktorom by najkratšia cesta zo štartu do cieľa mala dĺžku K. Na vstupe máme ale len nejaký nekvalitný pokus o bludisko s takou vlastnosťou. Preto sa budeme toto bludisko snažiť upraviť. Povolenou úpravou bude zmeniť nejaké políčko so stenou na chodbu alebo opačne. Nie je povolené meniť rozmery bludiska ani hýbať štart ani cieľ. Odlišnosť dvoch bludísk je celé číslo, ktoré hovorí, koľko políčok majú rôznych (za predpokladu, že majú rovnaké rozmery a pozície štartu a cieľa sa zhodujú).

Prvý riadok vstupu obsahuje 4 prirodzené čísla R,S,K a D. Platí 4 ≤ R,S ≤ 12, 1 ≤ K ≤ R·S a 1 ≤ D ≤ 3. Na ďalších R riadkoch nasleduje popis nejakého korektného bludiska. Každý z týchto riadkov obsahuje S znakov. Najkratšia cesta medzi štartom a cieľom nemusí existovať a ak existuje, môže mať ľubovoľnú dĺžku.

Ak existuje bludisko, ktoré má najkratšiu cestu zo štartu do cieľa dlhú K a nelíši sa od vstupného o viac ako D, potom prvý riadok výstupu má byť vo formáte Zmien: X, kde X je najmenší možný počet zmien, ktoré treba vykonať. Má platiť 0 ≤ X ≤ D. Na ďalších R riadkoch by mal byť popis korektného bludiska s požadovanými vlastnosťami. Toto bludisko by sa od vstupného malo líšiť v práve X znakoch. Ak je takých viac, vypíšte ľubovoľné. Ak požadované bludisko neexistuje, vypíšte NEDA SA. Pozor, časový limit je dosť tesný.

5 5 2 2
#####
#S..#
###.#
#C..#
#####

    
  

Zmien: 1
#####
#S..#
#.#.#
#C..#
#####

    
  

8 7 10 3
#######
#C....#
#.##.##
#.#..##
#.#####
#..#..#
#.S#..#
#######

    
  

Zmien: 3
#######
#C....#
####.##
#.#..##
#.##.##
#..#..#
#.S...#
#######

    
  

8 7 10 2
#######
#C....#
#.##.##
#.#..##
#.#####
#..#..#
#.S#..#
#######

    
  

NEDA SA